package com.mid;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * Created by Lxk on 2020/2/15.
 */
public class Solution210 {

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] inComeCount = new int[numCourses];
        //初始化入度记录表
        for (int[] arr : prerequisites) {
            inComeCount[arr[0]]++;
        }
        List<Integer> learned = new ArrayList<>();
        Queue<Integer> nodeQueue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            //寻找没有前驱课程（入度为0）的课添加到队列中
            if (inComeCount[i] == 0) {
                nodeQueue.offer(i);
            }
        }
        int countHasNotLearned = numCourses;
        //排除掉已经可以先学习的没有入度的课
        countHasNotLearned -= nodeQueue.size();
        while (!nodeQueue.isEmpty()) {
            int node = nodeQueue.poll();
            learned.add(node);
            for (int[] arr : prerequisites) {
                //寻找以node为起点的连接点，寻找node的邻居
                if (arr[1] != node) {
                    continue;
                }
                //邻居入度减一，判断是否此时入度为0；入度为0，则没有前驱课程，可以直接加入队列
                if (--inComeCount[arr[0]] == 0) {
                    nodeQueue.offer(arr[0]);
                    countHasNotLearned--;
                }
            }
        }
        int[] res = new int[0];
        if (countHasNotLearned == 0) {
            res = new int[learned.size()];
            for (int i = 0; i < learned.size(); i++) {
                res[i] = learned.get(i);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[][] arr = {{1, 0}, {0, 1}};
        Solution210 solution210 = new Solution210();
        System.out.println(solution210.findOrder(2, arr));
    }

}
